class Solution(object):
    def maximumNumberOfOnes(self, width, height, sideLength, maxOnes):
        """
        :type width: int
        :type height: int
        :type sideLength: int
        :type maxOnes: int
        :rtype: int
        """
        h_num = height // sideLength
        h_left = height % sideLength
        w_num = width // sideLength
        w_left = width % sideLength
        base = maxOnes * w_num * h_num
        if w_left == 0:
            if h_left == 0:
                return base
            else:
                return base + w_num * min(maxOnes, h_left * sideLength)
        else:
            if h_left == 0:
                return base + h_num * min(maxOnes, w_left * sideLength)
            else:
                if maxOnes <= w_left * h_left:
                    return base + (w_num + h_num + 1) * maxOnes
                else:
                    base += (w_num + h_num + 1) * w_left * h_left
                    maxOnes = maxOnes - w_left * h_left
                    w_un_cross = (sideLength - h_left) * w_left
                    h_un_cross = (sideLength - w_left) * h_left
                    s1 = min(maxOnes, w_un_cross) * h_num + min(max(0, maxOnes - w_un_cross), h_un_cross) * w_num
                    s2 = min(maxOnes, h_un_cross) * w_num + min(max(0, maxOnes - h_un_cross), w_un_cross) * h_num
                    return base + max(s1, s2)


data = Solution()
width = 3
height = 3
sideLength = 2
maxOnes = 1
print(data.maximumNumberOfOnes(width, height, sideLength, maxOnes))
